# This code is hosted on http://code.google.com/p/lenthorp/
# Freely available for use in applications, but should NOT be modified
# Email all comments to lenthorpresearch@gmail.com

from math import pow

# This is a recursive function that will continue to call itself until 1d is reached
def multiDimensionalLinearInterpolation(vals, dists):
    # algorithm assumes all arguments are passed in according to binary increments, e.g. For 3d [[0,0,0],[0,0,1],[0,1,0],[0,1,1],[1,0,0],[1,0,1],[1,1,0],[1,1,1]]
    # inputs:
    #   vals: list of the values at each of the nodes, in the order expected
    #   dists: list of the distances from each wall as pairs (left, right) in increasing dimension, e.g. for 3d [[0.1,0.9], [2.4,2.6], [0.08,0.02]]

    dim = len(dists)
    coords = len(vals)

    newDim = dim-1
    newVals = [0.0 for idx in range(int(pow(2,newDim)))]
    newDists = [dists[idx] for idx in range(len(dists)-1)]

    totalDist = dists[-1][1] + dists[-1][0]
    leftDist = dists[-1][0] / totalDist if totalDist > 1e-10 else 0.0
    rightDist = dists[-1][1] / totalDist if totalDist > 1e-10 else 0.0
    
    # For the final dimension, do the interpolation
    for idx in range(1, coords, 2):
        newVals[(idx-1)/2] = (vals[idx] * leftDist) + (vals[idx-1] * rightDist)

    if newDim > 0:
        return multiDimensionalLinearInterpolation(newVals, newDists)
    else:
        return newVals[0]
    
    